#include <iostream>
#include <vector>

using namespace std;

const int N = 15;

bool col[N], st1[N * 2], st2[N * 2];
int n;
vector<int> path;
int cnt = 0;

void dfs(int row)
{
	if(row > n)
	{
		cnt++;
		if(cnt <= 3)
		{
			for(auto x : path) cout << x << " ";
			cout << endl;
			return;
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(col[i] || st1[row + i] || st2[row - i + n]) continue;
		path.push_back(i);
		col[i] = st1[row + i] = st2[row - i + n] = true;
		dfs(row + 1);
		col[i] = st1[row + i] = st2[row - i + n] = false;
		path.pop_back();
		
	}
}

int main()
{
	cin >> n;
	
	dfs(1);
	cout << cnt << endl;
	return 0;
}
